package com.lenl.arithmetic.sort;

import java.util.Arrays;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-02 11:31
 * @description 归并排序 分治算法
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr={8,4,5,7,1,3,6,2};
        int[] temp=new int[arr.length]; //归并排序需要额外的空间
        doMergeSort(arr,0, arr.length-1,temp );

        System.out.println(Arrays.toString(arr));
    }

    //执行归并排序
    public static void doMergeSort(int[] arr,int left,int right,int[] temp){
        if(left<right){
            int mid=(left+right)/2;
            //向左递归分解
            doMergeSort(arr,left,mid,temp);
            //向右递归分解
            doMergeSort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }


    }

    /**
     *  归并的合并部分
     * @param arr 排序的原始数组
     * @param left 左边有序序列的初始索引
     * @param mid 中建索引
     * @param right 右边索引
     * @param temp 中转的数组
     */
    public static  void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i=left;//初始化i，左边有序序列的初始索引
        int j=mid+1;//初始化j，有边有序序列的初始索引
        int t=0; //temp中的当前索引
        //先把左右两边的数据（有序）按规则填充到temp数组，直到有一边全部处理完毕
        while(i<=mid&&j<=right){
            if(arr[i]<=arr[j]){
                temp[t]=arr[i];
                t+=1;
                i+=1;
            }else{
                temp[t]=arr[j];
                t+=1;
                j+=1;
            }
        }
        //把有剩余的一边依序填充到temp后面
        while(i<=mid){
            //左边全部填充
            temp[t]=arr[i];
            t+=1;
            i+=1;
        }
        while (j<=right){
            temp[t]=arr[j];
            t+=1;
            j+=1;
        }
        //将temp数组元素拷贝到arr
        t=0;
        int tempLeft=left;
        while(tempLeft<=right){
            arr[tempLeft]=temp[t];
            tempLeft+=1;
            t+=1;
        }

    }



}
